*247**853**1158*The concepts underlying dataflow computing emerged in the mid 1960s. But it was not until the early 1980s that dataflow programming became less an academic exercise and more a potential competitor to sequential-programming models. Very Large Scale Integration *1145* (VLSI)*1154* technology in computer-hardware development opened the door to enormous potentials in computing power. It was also quite clear that such potential would not be realized using traditional von Neumann computing architectures.
The von Neumann*1156* model is based on manipulating the state of a global memory using the sequential*358* execution*974* of a set of language commands. In VLSI, sequentially accessing global memory creates a tremendous bottleneck between the computer’s control unit and its memory. Thus, von Neumann architectures make it difficult for VLSI technology to approach even a fraction of its full computing capability. To reach such potential, alternative computing models have to be able to efficiently exploit concurrency*180* of computation on a very large scale. Dataflow architectures allow for concurrent*350* execution*184* at the simple program-instruction level. Thus, the dataflow model provides a key for tapping the power of VLSI hardware.11
What Makes Dataflow Languages Different?
A dataflow language*241* is any language either based entirely on the notion of data flowing from one function to another or directly supporting such flowing of data.12
In dataflow programming, data are active. They flow through the program and activate each instruction as soon as all the required input data have arrived. In the von Neumann model, data are passive*248*. They reside in memory waiting to be manipulated by instructions that are executed in a sequence controlled by a program counter.
Events in a dataflow program are not sequentially ordered. They can execute concurrently*185**351*. The basic instruction cycle*500* of any dataflow machine involves just four processes—detect, fetch, execute, and generate. The machine detects when all the required operand values are collected to enable an operation. The instruction for the operation to be performed is fetched. The operation is executed. And results are generated—data flows out, available to other instructions.
The dataflow firing rule is*239* implemented during the detect stage. This rule requires all arguments to be available before execution can take place. Arguments must be data. If data values are not yet available, the computing element remains dormant during the execute phase and does not try to execute the instruction.
 
Data flows through a Prograph program, activating each instruction as soon as all its required input data have arrived.
Although the basic instruction cycle *99*of every dataflow program is the same, there is tremendous flexibility in the details of exactly how this cycle is performed.13 In a von Neumann–based program cycle, there is a single thread of control passing from one instruction to another*100*. When control reaches an instruction, the operator is examined to determine the number of operands*789* and how they are used. The input addresses are referenced. The operator is executed and the result is stored in a memory cell. Finally, control is passed to the next instruction in sequence.
Most von Neumann*1157* architectures*249* are based on what is called an imperative*432* language model—in this case, a set of instructions that must be evaluated in a predetermined sequence. Under this model, a program is written to develop the sequence of control instructions that determine the order in which values are extracted from memory locations. Computations using these values are performed, and the resulting values are replaced in memory—values are reassigned to variables. This use of variables, with a reassigning of values to such variables, provides constraints on how instructions can be sequenced. It also inhibits concurrent computations.
The dataflow model allows more than one instruction to be executed simultaneously. The concurrency*181* in dataflow execution depends purely on the availability of data at instruction-execution time, the proportion of concurrency specified in the application to begin with, and how sufficient the computing resources are for handling concurrent executions. Because of this, dataflow programs are said to allow for fine-grain concurrency at the instruction level of a program.14
While Prograph is inherently concurrent due to its dataflow design, the Macintosh is a single-processor, and therefore sequential, machine. It is highly likely that a version of Prograph will be implemented to run on one or more of the parallel*819* multiprocessing*740* systems that are emerging in the marketplace. In such implementations, the parallel computer could provide the user-interface directly, or a host computer like the Macintosh could serve as a front-end system.
What Does a Dataflow Program Look Like?
*880*A dataflow program*1159* in a dataflow language is exclusively described by a directed graph*400* in which the nodes *758*represent operations and the arcs *78* represent dependencies between operations. The nodes of the graph represent individual instructions in the program, and data appear as input to these nodes. Any arithmetic or logical expression can be easily translated into a dataflow graph in a very straightforward manner.
It is easy to see why this architecture is called dataflow—the data appear to flow through the graph. It is carried from instruction to instruction by an abstract data carrier referred to as a token*236*. This token typically contains one data value, and it flows on an arc connecting two instruction nodes. When all of the data tokens required for execution arrive at the inputs of any instruction node, the dataflow firing rule comes into play. The instruction executes, and all data tokens are removed from the instruction-node inputs. Data that results from execution of this operation is then dispatched along an output arc and flows on to the input of a linked instruction node.
In Prograph, these nodes are called operations. They can be anything from a simple system-supplied primitive, such as addition, to a call to a user-defined method that can be arbitrarily complex. Since a method is itself a mini–dataflow program, a method with method-calling operations forms a nested hierarchy of dataflow. In this sense, Prograph is much more powerful and elaborate than dataflow languages that require nodes to be simple operations.
Each Prograph operation node can have one or more input terminals *1065* and one or more output roots.*955* Directed arcs between nodes, called*253* datalinks, connect node roots and terminals and define the path along which data flows in the dataflow program. Data travels a path*226* from operation node to operation node, from roots to terminals, by way of datalinks. When all the required input data arrives at any operation node, the operation executes. As different data travel along several different paths simultaneously, concurrent*352* execution of several operations is likely to occur.
 
Operations without data dependencies can be executed concurrently*182**186*.
Dataflow programs do not prescribe a specific order of execution as do assignment-based programs. They specify only the essential dependencies between data. A data dependency *225*is defined as the dependence of the data at an operation-node output (a Prograph root) on the data at the operation-node input (a Prograph terminal). If there is no path from one datalink to another, then functions producing those data can be executed concurrently. Dataflow programs are implicitly driven by data.
There are two main implementations of the general dataflow model; static and dynamic architectures. Static dataflow allows at most one data value per arc in dataflow graphs. Dynamic dataflow architectures keep a number of data values in a common pool on an arc, uniquely tagging each value for easy recognition. As the data pool arrives on the input of an instruction node, the appropriate data value required by the program instruction is recognized and the firing rule kicks in.
Prograph is a dynamic dataflow language. As you may have noticed in the Grand Tour, and as you will see in Part 2, “Tutorials,” more than one data value flows along a Prograph datalink. Data travelling along datalinks in a Prograph program can be either elementary data types, like integers or strings, or complex objects, instances of object-oriented classes. This ability to flow both objects and elementary data values is why Prograph can be further described as an objectflow language.
 
In Prograph’s dynamic dataflow architecture, a single object entering an operation can encapsulate a complex data structure of objects within objects.
Operations are enabled for execution as soon as data tokens are placed on the input datalinks. Two unconnected operations can fire simultaneously, or one can fire before the other. The results are the same in either case: the result of an operation is purely a function of the input values. In a pure dataflow language, there are no implicit interactions between operations by means of side*987* effects, for example, through shared memory. *881*Prograph, like a growing number of dataflow implementations, does support such features as persistent objects, which provide the opportunity for side effects. (Prograph’s online documentation of primitives notes and explains the relatively few operations that have potential side effects.)
Two particularly interesting properties of the general dataflow model*243* involve parallelism *820*and independence.*434* In dataflow programs, operations can potentially execute in parallel. Unless there is an explicit data dependence between operations, each operation executes whenever its required input data becomes available. Further, overall results are independent of the relative order in which parallel nodes execute unless there is an explicitly specified sequence in the program.
As a dataflow language, Prograph diagrams are also inherently parallel and independent. And Prograph provides synchros *1031*so you can control the relative order*245* in which operations execute when desired.
In essence, the key features*242* of dataflow languages that make them particularly interesting and powerful include:
o Results are passed directly as data tokens between instructions.
o Execution consumes data tokens, that is, used data values are no longer directly available as inputs to other instructions.
o There is no concept of shared data as embodied in the traditional notion of a variable. (Although Prograph supports class attributes and persistent objects for added flexibility, their use is not required.)
o Flow of control and flow of data are identical.
o Concurrent*353**183**187* execution can occur at the instruction level of a program.
Even with these advantages, for those not used to programming graphically, dataflow diagrams may at first seem intimidating. But program graphs can be easily teased apart to see every operation. *779*Since Prograph supports the visual display of dataflow methods during their execution*246*, you can gain a quick appreciation for what they express and how they work. And through the use of operations calling other methods and local methods within methods, a great deal of information can be expressed in extremely simple graphs. You have a great deal of control over how much detail you show in the execution cycle of your programs.
 
Prograph dataflow methods can be nested into simpler, logical graphs.
The use of graphical tools for software development is gaining momentum. When these tools are used in the context of a dataflow language, as is done in Prograph, there is a clear synergistic advantage.
Dataflow graphs do not merely represent a text-language base for such functions as procedure nesting, loops, calling sequences, and so on. The graphs themselves have a well-defined functional meaning: they are the executable code specifying the system being developed.
When graphical tools for debugging, monitoring, and resource management are used in conjunction with dataflow-program graphs, programs can be developed more productively and efficiently than is currently possible.15 And with today’s available desktop computing power, such productivity is well within reach of nonprogramming professionals.
As you explore the dataflow power of the Prograph language in the following tutorial sections, you may be surprised at how quickly you become proficient at specifying complex operations in a dataflow language. When you add to that language the capabilities of both object-oriented and visual programming, you have an incredibly powerful programming tool.
We have considered dataflow programming as a potential architecture for meeting the requirements demanded of programming languages for *1146* VLSI*1155* technology. There is much more to learn about dataflow programming than can be covered in this chapter. If you would like to read more about this topic, please refer to the “References” section at the end of this chapter.
